package leetcode.day;
// 1020. 飞地的数量

/**
 * 解题思路:
 * DFS
 * 每个边缘点进行DFS，每个点设置为0. 边缘点都进行上下左右的移动。
 * 在遍历一下内部的点，统计非0的个数
 */
public class NumEnclaves {
    public static void main(String[] args) {
        int[][] data = {{0,1,1,0},{0,0,1,0},{0,0,1,0},{0,0,0,0}};
        System.out.println(numEnclaves(data));
        
    }
    static int[] dx = new int[]{-1, 1, 0, 0};
    static int[] dy = new int[]{0, 0, -1, 1};

    public static int numEnclaves(int[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if ((i == 0 || i == grid.length - 1 || j == 0 ||
                        j == grid[0].length - 1)
                        && grid[i][j] == 1) {
                    dfs(grid, i, j);
                }
            }
        }
        int res = 0;
        for (int i = 1; i < grid.length - 1; i++) {
            for (int j = 1; j < grid[0].length - 1; j++) {
                if (grid[i][j] == 1) {
                    res++;
                }
            }
        }
        return res;

    }

    private static void dfs(int[][] grid, int x, int y) {
        grid[x][y] = 0;
        for (int i = 0; i < 4; i++) {
            int mx = dx[i] + x;
            int my = dy[i] + y;
            if (mx >= 0 && mx < grid.length && my >= 0 && my < grid[0].length && grid[mx][my] == 1) {
                dfs(grid, mx, my);
            }
        }

    }
}
